# 最低有效位
# i >> 1  ===> 其二进制表示的最低位去掉
# 得到 x/2
# 如果 bits[x/2]的值已知，则可以得到 bits[x] 的值
# 如果 xx 是偶数，则 bits[x] = bits[x/2]
# 如果 xx 是奇数，则 bits[x] = bits[x/2] + 1
# 由于 x/2 可以通过 x >> 1得到  x除以2的余数可以通过 x&1 得到
# 因此 bits[x]= bits[x>>1]+ (x&1)


def countBits(n):
    bits = [0]
    for i in range(1, n + 1):
        bits.append(bits[i >> 1] + (i & 1))
    return bits


print(countBits(2))  # [0,0,1]
print(countBits(5))  # [0,1,1,2,1,2]
